package dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 494. 目标和
 */
public class P494 {
    public int findTargetSumWays(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        Map<Integer, Integer> tmpMap = new HashMap<>();
        tmpMap.put(0, 1);
        for (int num : nums) {
            Map<Integer, Integer> map = new HashMap<>();
            for (Map.Entry<Integer, Integer> entry : tmpMap.entrySet()) {
                int newKey = entry.getKey() + num;
                int newVal = entry.getValue() + map.getOrDefault(newKey, 0);
                map.put(newKey, newVal);
                //
                newKey = entry.getKey() - num;
                newVal = entry.getValue() + map.getOrDefault(newKey, 0);
                map.put(newKey, newVal);
            }
            tmpMap = map;
        }
        return tmpMap.entrySet().stream().mapToInt(entry -> {
            return entry.getKey() == target ? entry.getValue() : 0;
        }).sum();
    }

    public static void main(String[] args) {
        int targetSumWays = new P494().findTargetSumWays(new int[]{17,13,31,50,8,40,5,13,20,45,18,45,0,28,31,39,23,13,24,2}, 35);
        System.out.println(targetSumWays);
    }

}
